class Solution {
    public:
        int findNumberOfLIS(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> dp(n,vector<int>(2,1));
            //dp[i][0]表示已i位置为结尾的最长递增子序列个数，dp[i][1]表示已i位置为结尾的最长递增子序列长度
            int ret = 1,maxlenth = 1;
            dp[0][0]=dp[0][1] = 1;
            for(int i = 1 ; i < n ; i++){
                int lastmaxlenth = 0;
                for(int j = i-1 ; j >= 0 ; j--){
                    if(nums[i] > nums[j]){
                        if(dp[j][1] > lastmaxlenth){
                            dp[i][0] = dp[j][0];
                            dp[i][1] = dp[j][1]+1;
                            lastmaxlenth = dp[j][1];
                        }else if(dp[j][1] == lastmaxlenth){
                            dp[i][0] += dp[j][0];
                        }
                    }
                }
                if(maxlenth < dp[i][1]){
                    ret = dp[i][0];
                    maxlenth = dp[i][1];
                }else if(maxlenth == dp[i][1]){
                    ret += dp[i][0];
                }
                
            }
    
            return ret;
        }
    };